home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 7 / BBS in a Box - Macintosh - Volume VII (BBS in a Box) (January 1993).iso / Files / Prog / Q-R / R⁄O strsml.cpt / Ratcliff_Obershelp / strsml1.c < prev    next >
Text File  |  1989-01-12  |  2KB  |  69 lines
  1. /*
  2.     simil(s1, s2) - returns a value signifying how similar two 
  3.         strings are (0 - completely different, 100 - exactly the same)
  4.         using the Ratcliff/Obershelp pattern matching algorithm.
  5.         
  6.     (Code courtesy of Rick Orsborn published in DDJ, Nov 1988, #145, pg.12, 118).
  7. */
  8. int simil(s1, s2)
  9.     char *s1, *s2;
  10.     {
  11.     short l1, l2;
  12.     
  13.     l1 = strlen(s1);
  14.     l2 = strlen(s2);
  15.     
  16.     if (l1 == 1)                        /*    check for the easiest case    */
  17.         if (l2 ==1)
  18.             if (*s1 == *s2)
  19.                 return (100);
  20.  
  21.     return (200 * GCsubstr(s1, s1 + l1, s2, s2 + l2) / (l1 + l2));
  22.     }
  23.     
  24. /*
  25.     GCsubstr(st1, end1, st2, end2) - returns the length of the greatest
  26.         common substring using recursion.  st1 and st2 are the two strings. 
  27.         end1 and end2 are pointers to the ends of the strings.
  28. */
  29. int GCsubstr(st1, end1, st2, end2)
  30.     char *st1, *end1, *st2, *end2;
  31.     {
  32.     register char *a1, *b1, *s1, *a2, *b2, *s2;
  33.     short max, i;
  34.     
  35.     if (end1 <= st1)                    /*    st1 is empty    */
  36.         return (0);
  37.     if (end2 <= st2)                    /*    st2 is empty    */
  38.         return (0);
  39.     if (end1 == st1 + 1)                /*    if s1 has one char            */
  40.         if (end2 == st2 + 1)            /*        and s2 has one char,    */
  41.             return (0);                    /*        they cannot be equal    */
  42.     
  43.     max = 0;
  44.     b1 = end1;
  45.     b2 = end2;
  46.     
  47.     for (a1 = st1; a1 < b1; a1++)
  48.         for (a2 = st2; a2 < b2; a2++)
  49.             if (*a1 == *a2)
  50.                 {
  51.                 for (i = 1; a1[i] && (a1[i] == a2[i]); i++)
  52.                     /*    how long is the common substring?    */;
  53.                 if (i > max)
  54.                     {
  55.                     max = i;
  56.                     s1 = a1;
  57.                     s2 = a2;
  58.                     b1 = end1 - max;
  59.                     b2 = end2 - max;
  60.                     }
  61.                 }
  62.     if (! max)
  63.         return (0);
  64.         
  65.     max += GCsubstr(s1 + max, end1, s2 + max, end2);    /*    right substring    */
  66.     max += GCsubstr(st1, s1, st2, s2);                /*    left substring    */
  67.     
  68.     return (max);
  69.     }